home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 332_01 / euclid.c < prev    next >
C/C++ Source or Header  |  1990-03-28  |  4KB  |  163 lines
  1. /*----------------------------------------------------*- Fundamental -*-
  2.  
  3. Facility:        euclid
  4.  
  5. File:            euclid.c
  6.  
  7. Associated files:    - (none)
  8.  
  9. Description:        This is an implementation of the algorithm
  10.             1.1E given in [1] describing a solution
  11.             (by Euclid) to the problem of finding the
  12.             greatest common    denominator for two given
  13.             integers.
  14.  
  15. Portability:        Conforms to X/Open Portability Guide, ed. 3,
  16.  
  17. References:        [1] Knuth, Donald E:
  18.             The Art of Computer Programming,
  19.               Vol. 1 - Fundamental Algorithms, ed. 2,
  20.             Addison-Wesley, 1968
  21.  
  22.             [2] X/Open Company, Ltd:
  23.               X/Open Portability Guide, ed. 3 (7 vol)
  24.             Prentice-Hall, 1989
  25.  
  26. Author:            H. Moran (?)
  27.  
  28. Editor:            Anders Thulin
  29.             Rydsvagen 288
  30.             S-582 50 Linkoping
  31.             SWEDEN
  32.  
  33. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  34.  
  35. Edit history :
  36.  
  37. Vers  Ed   Date           By                Comments
  38. ----  ---  ----------  ----------------  -------------------------------
  39.  1.0    0  19xx-xx-xx  H. Moran (?)
  40.  1.1    1  1988-10-25  Anders Thulin      :>
  41.  
  42.     Did not compile under K&R: General cleanup: changed to
  43.     K&R syntax, added include files, some cleanup of logic,
  44.     removed unnecessary variables, added some error checking. 
  45.  
  46. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  47.  
  48. /*---  Configuration:  -------------------------------------------------
  49.  
  50. System configuration:
  51. =====================
  52.  
  53.   ANSI        ANSI C, 
  54.   BSD        BSD Unix, SunOS 3.5
  55.   SV2        AT&T UNIX System V.2, AU/X
  56.   XPG3        X/Open Portability Guide, ed. 3
  57.  
  58. If you have an ANSI C compiler, define ANSI.  Otherwise, define the
  59. system that best matches your environment.
  60.  
  61.  
  62. Program configuration:
  63. ======================
  64.  
  65.   INPUT_LEN    The max length of an input line
  66.  
  67. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  68.  
  69. #define    ANSI    1
  70. #define    BSD    0
  71. #define    SV2    0
  72. #define    XPG3    0
  73.  
  74. #define    INPUT_LEN    160    /* characters */
  75.  
  76. /* - - End: configuration options - - - - - - - - - - - - - - - - - - - - - */
  77.  
  78. #if ANSI
  79. # include <stdio.h>
  80. # include <stdlib.h>
  81. #endif
  82.  
  83. #if BSD
  84. # include <stdio.h>
  85. # define EXIT_SUCCESS    0
  86.   extern long strtol();
  87. #endif
  88.  
  89. #if SV2
  90. # include <stdio.h>
  91. # define EXIT_SUCCESS    0
  92.   extern long strtol();
  93. #endif
  94.  
  95. #if XPG3
  96. # include <stdio.h>
  97. # include <stdlib.h>
  98. #endif
  99.  
  100. /*----------------------------------------------------------------------
  101.  
  102. Routine:    main
  103.  
  104. Description:    main program
  105.  
  106. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  107.  
  108. int main()
  109. {
  110.   long r, m, n;
  111.   long temp;
  112.   char string[INPUT_LEN];    /* input string */
  113.  
  114.   puts("euclid - computes largest common divisor of two integers");
  115.  
  116.   /*  1.  Job loop:  */
  117.  
  118.   while (1) {
  119.  
  120.    /*
  121.     *  1a.  Get the two numbers m and n.
  122.     *
  123.     *  Note that using gets() is in general bad practice - there
  124.     *  is no check that input doesn't overrun the input buffer and
  125.     *  destroys important info.  fgets() is better.
  126.     *
  127.     */
  128.  
  129.     printf("\nenter first integer  ( > 0) : ");
  130.     m = strtol(gets(string), (char **)0, 10);
  131.     if (m <= 0) break;
  132.  
  133.     printf("enter second integer ( > 0) : ");
  134.     n = strtol(gets(string), (char **)0, 10);
  135.     if (n <= 0) break;
  136.  
  137.     /*  1b.  Ensure that m >= n:  */
  138.  
  139.     if (m < n)  {
  140.       temp = m;
  141.       m = n;
  142.       n = temp;
  143.     }
  144.  
  145.     /*  1c.  Euclid's algorithm:  */
  146.  
  147.     r = m % n;
  148.     while (r != 0) {
  149.       m = n;
  150.       n = r;
  151.       r = m % n;
  152.     }
  153.  
  154.     printf("\nlargest common divisor = %ld\n", n);
  155.  
  156.   }
  157.  
  158.   /*  2.  Terminate nicely:  */
  159.  
  160.   return EXIT_SUCCESS;                    
  161. }
  162.  
  163.